package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 和为S的两个数字 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：439072
 * 本题知识点： 数学 数组 双指针
 *  算法知识视频讲解
 * 题目描述
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 * 返回值描述:
 * 对应每个测试案例，输出两个数，小的先输出。
 * 示例1
 * 输入
 * 复制
 * [1,2,4,7,11,15],15
 * 返回值
 * 复制
 * [4,11]
 */
public class FindNumbersWithSum {

    @Test
    public void test() {
        System.out.println(FindNumbersWithSum(new int[]{1,2,4,7,11,15},15));
    }
     //居然超时了。。。(原来是被题目误导了) 使用双指针解决问题：
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {

        ArrayList<Integer> result = new ArrayList<>();

        if (array.length == 0 || array[0] >= sum) {
            return result;
        }

        int i = 0;
        int j = array.length-1;


        while (i!=j) {
            if (array[i] + array[j] == sum) {
                if (result.isEmpty()) {
                    result.add(array[i++]);
                    result.add(array[j--]);
                    break;
                }
            } else if (array[i] + array[j] < sum) {
                i++;
            } else {
                j--;
            }
        }

        return result;
    }
}
